package A.动态数组;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class _268_丢失的数字 {

    /**
     * 自借：排序--时间复杂度略大
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {

        if (nums.length==0){
            return 0;
        }
        Arrays.sort(nums);

        if (nums[nums.length-1] !=  nums.length){
            return nums.length;
        }else {
            for (int i=0;i<nums.length;i++){
                //下标不匹配了
                if (i != nums[i]){
                    return i;
                }
            }
        }
        return 0;

    }

    /**
     * hash法：用hashset来做 set跟map类似 但是只存一个参数 元素类似于key 因此不能重复
     * @param nums
     * @return
     */
    public int missingNumber1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i= 0;i<nums.length;i++){
            set.add(nums[i]);
        }

        int findNum = nums.length+1;
        for (int i=0;i<findNum;i++){
            if (!set.contains(i)){
                return i;
            }
        }

        return -1;


    }

    /**
     * 考虑数学方法：用0-n求和得到应该总和 减去 数组所有的和 就得到缺失的数字
     */
    public int missingNumber2(int[] nums) {
         int actualSum = (nums.length+0)*(nums.length+1)/2;
         int sum=0;
         for (int num:nums){
             sum += num;
         }

         return actualSum-sum;
    }


}
